Internet Protocol (IP) networks need to support real-time applications that require stringent availability and reliability, such as Voice over IP and virtual private networks. Networks are made up of a plurality of nodes connected by links. If any one node or link fails, network traffic needs to be rerouted along alternative paths through the network. Failures are common in the daily operation of networks, for reasons such as improper configuration, faulty interfaces, accidental fiber cuts and the like. Therefore, mechanisms that restore the flow of traffic quickly and efficiently after a failure are essential.
In restoration mechanisms using typical IP routing protocols, a node first detects a failure and then disseminates routing updates to other nodes. These updates are used for calculating new paths. This process may take several seconds before proper routing of data can resume. During this time, packets destined to some destinations may be dropped, and applications might be disrupted. Moreover, when Quality of Service (QoS) is supported, the routing protocol cannot guarantee that the alternate path will provide the same QoS as the failed one. Thus IP routing protocols are not suitable for fast restoration.
Consequently, network operators often employ recovery mechanisms in protocols such as WDM, SONET/SDH, and MPLS. These additional recovery mechanisms may provide fast restoration and high QoS assurance by establishing backup paths in advance, before a failure event takes place. Such recovery mechanisms are usually referred to as “protection” mechanisms, as opposed to “rerouting” mechanisms, which establish backup paths only after a failure occurs.
Prior art mechanisms for selecting optimal backup paths typically aim to minimize the total bandwidth reserved for the backup paths. To this end, backup paths are routed in such a way as to maximize their bandwidth sharing. This optimization metric is usually referred to as Spare Capacity Allocation (SCA).
Models that seek to optimize SCA usually consider a network whose links have unbounded capacity, and a cost function associated with bandwidth usage. In SCA optimization the cost associated with an established LSP does not depend on the load imposed on the selected route. There is therefore no incentive for load balancing. Such unbounded capacity models are useful for network designers as they may be used to determine the required capacity of the network under design.
Unlike network designers, network operators often need to use pre-existing networks with given capacities. Typically, the network operator seeks to maximize revenue by maximizing the traffic carried by a given network with finite link capacities. SCA optimization is not suited to such scenarios. The need remains, therefore, for a mechanism for quickly and efficiently restoring the flow of traffic after failure in fixed capacity networks. The present invention addresses this need.